#include <iostream>
#include <stdio.h>

#include <iostream>
#include <vector>

class Solution {
private:
    std::vector<std::vector<std::string>> result;
    // std::vector<int> path;
    // n 为棋盘大小  
    //row是当前递归到棋盘的第几行
    void backtracking (int n, int row, std::vector<std::string>& chessboard) {
        if(row == n){
            result.push_back(chessboard);
            return;
        }
        for (int col = 0; col < n; col++) {
            if(isValid(row, col, chessboard, n)){
                chessboard[row][col] = 'Q';
                backtracking(n, row+1,chessboard);
                chessboard[row][col] = 'N';
            }

            
        }
    }

    bool isValid(int row,int col, std::vector<std::string> chessboard, int n)
    {
        // 检查列
        for (int i = 0; i < row; i++) { // 这是一个剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 检查 45度角是否有皇后
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 检查 135度角是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        result.clear();
        std::vector<std::string> chessboard(n,std::string(n, 'N'));
        backtracking(n, 0, chessboard);
        return result;
    }
};

int main(int argv, char**argc)
{

    printf("************  test hello zc!!!   **************\n");
    /* add test code! */
    Solution solve;
    std::vector<std::vector<std::string>> ret;

    ret = solve.solveNQueens(8);
    // printf("[ ");
    for(auto p:ret){
        // printf("[");
        for(auto q:p){
            printf("%s \n", q.c_str());
        }
        printf("===== \n");    
    }
    printf("%ld\n", ret.size());
    return 0;
}
